{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Create a balanced binary search tree\n",
    "\n",
    "[The Original Question](https://mp.weixin.qq.com/s/BnXFdK09kukSs6jGHfb8VQ)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "Given a sorted list of numbers, change it into a balanced binary search tree. You can assume there will be no duplicate numbers in the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "```text\n",
    "Input: [1, 2, 3, 4, 5, 6, 7]\n",
    "Output: 4261357\n",
    "```\n",
    "\n",
    "The visual structure of the balanced binary search tree is shown below:\n",
    "\n",
    "```text\n",
    "     4\n",
    "   /   \\\n",
    "  2     6\n",
    " / \\   / \\\n",
    "1   3 5   7\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def __str__(self):\n",
    "        # level-by-level pretty-printer\n",
    "        nodes = deque([self])\n",
    "        answer = ''\n",
    "        while len(nodes):\n",
    "            node = nodes.popleft()\n",
    "            if not node:\n",
    "                continue\n",
    "            answer += str(node.value)\n",
    "            nodes.append(node.left)\n",
    "            nodes.append(node.right)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def createBalancedBST(nums):\n",
    "    # Count the length of the given array.\n",
    "    length = len(nums)\n",
    "    if length == 1:\n",
    "        return Node(nums[0])\n",
    "    else:\n",
    "        # Find the middle of the given array.\n",
    "        middle = length // 2 + length % 2 - 1\n",
    "        temp_tree = Node(nums[middle])\n",
    "        temp_tree.left = createBalancedBST(nums[:middle])\n",
    "        temp_tree.right = createBalancedBST(nums[middle + 1:])\n",
    "        return temp_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4261357\n"
     ]
    }
   ],
   "source": [
    "print(createBalancedBST([1, 2, 3, 4, 5, 6, 7]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes\n",
    "\n",
    "Accroding to the definition of a balanced binary search tree, the root node of a (sub)tree is the middle element of the given sorted array and its two children are two subarrays located in both sides of the middle element.\n",
    "\n",
    "Using this regulation, we can create a complete balenced binary search tree recursively. \n",
    "\n",
    "*Challenge: If you have a non-recursively algorighm, please tell me. Thank you!*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
